{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Can Make Palindrome from Substring"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #bit-manipulation #array #hash-table #string #prefix-sum"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #位运算 #数组 #哈希表 #字符串 #前缀和"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: canMakePaliQueries"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #构建回文串检测"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个字符串&nbsp;<code>s</code>，请你对&nbsp;<code>s</code>&nbsp;的子串进行检测。</p>\n",
    "\n",
    "<p>每次检测，待检子串都可以表示为&nbsp;<code>queries[i] = [left, right, k]</code>。我们可以 <strong>重新排列</strong> 子串&nbsp;<code>s[left], ..., s[right]</code>，并从中选择 <strong>最多</strong> <code>k</code>&nbsp;项替换成任何小写英文字母。&nbsp;</p>\n",
    "\n",
    "<p>如果在上述检测过程中，子串可以变成回文形式的字符串，那么检测结果为&nbsp;<code>true</code>，否则结果为&nbsp;<code>false</code>。</p>\n",
    "\n",
    "<p>返回答案数组&nbsp;<code>answer[]</code>，其中&nbsp;<code>answer[i]</code>&nbsp;是第&nbsp;<code>i</code>&nbsp;个待检子串&nbsp;<code>queries[i]</code>&nbsp;的检测结果。</p>\n",
    "\n",
    "<p>注意：在替换时，子串中的每个字母都必须作为 <strong>独立的</strong> 项进行计数，也就是说，如果&nbsp;<code>s[left..right] = &quot;aaa&quot;</code>&nbsp;且&nbsp;<code>k = 2</code>，我们只能替换其中的两个字母。（另外，任何检测都不会修改原始字符串 <code>s</code>，可以认为每次检测都是独立的）</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>s = &quot;abcda&quot;, queries = [[3,3,0],[1,2,0],[0,3,1],[0,3,2],[0,4,1]]\n",
    "<strong>输出：</strong>[true,false,false,true,true]\n",
    "<strong>解释：</strong>\n",
    "queries[0] : 子串 = &quot;d&quot;，回文。\n",
    "queries[1] :&nbsp;子串 = &quot;bc&quot;，不是回文。\n",
    "queries[2] :&nbsp;子串 = &quot;abcd&quot;，只替换 1 个字符是变不成回文串的。\n",
    "queries[3] :&nbsp;子串 = &quot;abcd&quot;，可以变成回文的 &quot;abba&quot;。 也可以变成 &quot;baab&quot;，先重新排序变成 &quot;bacd&quot;，然后把 &quot;cd&quot; 替换为 &quot;ab&quot;。\n",
    "queries[4] :&nbsp;子串 = &quot;abcda&quot;，可以变成回文的 &quot;abcba&quot;。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= s.length,&nbsp;queries.length&nbsp;&lt;= 10^5</code></li>\n",
    "\t<li><code>0 &lt;= queries[i][0] &lt;= queries[i][1] &lt;&nbsp;s.length</code></li>\n",
    "\t<li><code>0 &lt;= queries[i][2] &lt;= s.length</code></li>\n",
    "\t<li><code>s</code> 中只有小写英文字母</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [can-make-palindrome-from-substring](https://leetcode.cn/problems/can-make-palindrome-from-substring/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [can-make-palindrome-from-substring](https://leetcode.cn/problems/can-make-palindrome-from-substring/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['\"abcda\"\\n[[3,3,0],[1,2,0],[0,3,1],[0,3,2],[0,4,1]]', '\"lyb\"\\n[[0,1,0],[2,2,1]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canMakePaliQueries0(self, s: str, queries: List[List[int]]) -> List[bool]:\n",
    "        n = len(s)\n",
    "        pre = [[0] * (n+1) for _ in range(26)]\n",
    "        for i,x in enumerate(s):\n",
    "            cur = ord(x) - ord('a')\n",
    "            for y in range(26):\n",
    "                pre[y][i+1] = pre[y][i]\n",
    "                if cur == y:\n",
    "                    pre[y][i+1] += 1\n",
    "\n",
    "        ans = []\n",
    "        for l,r,k in queries:\n",
    "            m = 0\n",
    "            for i in range(26):\n",
    "                if (pre[i][r+1] - pre[i][l]) % 2 == 1:\n",
    "                    m += 1\n",
    "            ans.append(m//2 <=k)\n",
    "        return ans\n",
    "\n",
    "    def canMakePaliQueries(self, s: str, queries: List[List[int]]) -> List[bool]:\n",
    "        # 位运算优化\n",
    "        '''\n",
    "        n = len(s)\n",
    "        pre = [0] * (n+1)\n",
    "        for i,x in enumerate(s):\n",
    "            w = 1 << (ord(x) - ord('a'))\n",
    "            pre[i+1] = pre[i] ^ w\n",
    "        '''\n",
    "        pre = [0]\n",
    "        for i,x in enumerate(s):\n",
    "            w = 1 << (ord(x) - ord('a'))\n",
    "            pre.append(pre[-1] ^ w)\n",
    "\n",
    "        ans = []\n",
    "        for l,r,k in queries:\n",
    "            m = (pre[r+1] ^ pre[l]).bit_count()\n",
    "            ans.append(m//2 <= k)\n",
    "\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canMakePaliQueries(self, s: str, queries: List[List[int]]) -> List[bool]:\n",
    "        reslist = []\n",
    "        abcnum = {}\n",
    "        abcnum[-1] = 0\n",
    "        for idx, stri in enumerate(s):\n",
    "            abcnum[idx] = abcnum[idx-1] ^ (1 << (ord(stri) - ord('a')))\n",
    "        # print(abcnum)\n",
    "        for query in queries:\n",
    "            startid = query[0]\n",
    "            endid = query[1]\n",
    "            maxnum = query[2]\n",
    "            strdict = {}\n",
    "            sumres = 0\n",
    "            tempres = abcnum[endid] ^ abcnum[startid-1]\n",
    "            while tempres > 0:\n",
    "                sumres += tempres % 2\n",
    "                tempres = tempres >> 1\n",
    "            if sumres // 2 > maxnum:\n",
    "                reslist.append(False)\n",
    "            else:\n",
    "                reslist.append(True)\n",
    "        return reslist"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canMakePaliQueries(self, s: str, queries: List[List[int]]) -> List[bool]:\n",
    "        n = len(queries)\n",
    "        ans = [False] * n\n",
    "        sm = [0]\n",
    "        for c in s:\n",
    "            bit = 1 << ord(c) - ord('a')  # 状态压缩\n",
    "            sm.append(sm[-1] ^ bit)\n",
    "        @cache\n",
    "        def f(l, r, k):\n",
    "            cnt = (sm[r + 1] ^ sm[l]).bit_count()\n",
    "            return k >= cnt // 2\n",
    "        for i in range(n):\n",
    "            ans[i] = f(queries[i][0], queries[i][1], queries[i][2])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canMakePaliQueries(self, s: str, qs: List[List[int]]) -> List[bool]:\n",
    "        N, M = len(s), len(qs)\n",
    "        ai2odds = [[False] + [None for _ in range(N)] for _ in range(26)]\n",
    "        for ci, c in enumerate(s):\n",
    "            for ai in range(26):\n",
    "                ai2odds[ai][ci+1] = ai2odds[ai][ci]\n",
    "                if ord(c) - ord('a') == ai:\n",
    "                    ai2odds[ai][ci+1] = not ai2odds[ai][ci+1]\n",
    "        ans = [None for _ in range(M)]\n",
    "        for qi, (lft, rgt, k) in enumerate(qs):\n",
    "            n = 0\n",
    "            for ai in range(26):\n",
    "                if ai2odds[ai][lft] ^ ai2odds[ai][rgt+1]: n += 1\n",
    "            ans[qi] = n // 2 <= k\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canMakePaliQueries(self, s: str, queries: List[List[int]]) -> List[bool]:\n",
    "        size = len(s)\n",
    "        state = []\n",
    "        for i in range(26):\n",
    "            state.append([0] + [0 for _ in range(size)])\n",
    "\n",
    "        for idx, i in enumerate(s):\n",
    "            for char in range(26):\n",
    "                state[char][idx+1] = state[char][idx]\n",
    "                if char == ord(i) - ord('a'):\n",
    "                    state[char][idx+1] += 1\n",
    "\n",
    "        res = []\n",
    "        for l, r, k in queries:\n",
    "            cnt = 0\n",
    "            for i in range(26):\n",
    "                cnt += (state[i][r+1] - state[i][l]) % 2\n",
    "            res.append(cnt // 2 <= k)\n",
    "        return res\n",
    "\n",
    "            \n",
    "\n",
    "    def check(self, s: str):\n",
    "        cnt = {}\n",
    "        for i in s:\n",
    "            if i not in cnt:\n",
    "                cnt[i] = 0\n",
    "            cnt[i] += 1\n",
    "        res = 0\n",
    "        for k, v in cnt.items():\n",
    "            if v % 2 == 0:\n",
    "                continue\n",
    "            res += 1\n",
    "        return res//2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canMakePaliQueries(self, s: str, queries: List[List[int]]) -> List[bool]:\n",
    "        cnt = [0]\n",
    "        for i, v in enumerate(s):\n",
    "            cnt.append(cnt[i] ^ 1 << (ord(v) - 97))\n",
    "        return [bin(cnt[i] ^ cnt[j + 1]).count('1') // 2 <= k for i, j, k in queries]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canMakePaliQueries(self, s: str, queries: List[List[int]]) -> List[bool]:\n",
    "        tab = [[False]*26]\n",
    "        for i in range(len(s)):\n",
    "            tab.append(tab[i][:])\n",
    "            tab[i+1][ord(s[i])-ord('a')] = not tab[i+1][ord(s[i])-ord('a')] \n",
    "        return [sum((tab[hi+1][i]^tab[lo][i] ) for i in range(26)) //2 <= k for lo, hi, k in queries]\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canMakePaliQueries(self, s: str, queries: List[List[int]]) -> List[bool]:\n",
    "        res, sm = [[0]*26], []\n",
    "        for i in s:\n",
    "            res.append(res[-1][:])\n",
    "            num = ord(i)-97\n",
    "            res[-1][num] = 1 - res[-1][num]\n",
    "        for x,y,z in queries:\n",
    "            p = 0\n",
    "            for i,j in zip(res[x],res[y+1]):\n",
    "                if i!=j: p += 1\n",
    "            sm.append(p//2<=z)\n",
    "        return sm\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canMakePaliQueries(self, s: str, queries: List[List[int]]) -> List[bool]:\n",
    "        record = [[0] for _ in range(26)]\n",
    "        for cha in s:\n",
    "            for i in range(26):\n",
    "                if i == ord(cha) - ord('a'):\n",
    "                    record[i].append(record[i][-1] + 1)\n",
    "                else:\n",
    "                    record[i].append(record[i][-1])\n",
    "        result = []\n",
    "        for q in queries:\n",
    "            l, r, k = q\n",
    "            odd = 0\n",
    "            for i in range(26):\n",
    "                cha_num = record[i][r + 1] - record[i][l]\n",
    "                if cha_num % 2 == 1:\n",
    "                    odd += 1\n",
    "            if odd // 2 <= k:\n",
    "                result .append(True)\n",
    "            else:\n",
    "                result.append(False)\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canMakePaliQueries(self, s: str, queries: List[List[int]]) -> List[bool]:\n",
    "        preSums = [[0] * 26]\n",
    "        for c in s:\n",
    "            preSums.append(preSums[-1].copy())\n",
    "            preSums[-1][ord(c) - 97] += 1\n",
    "\n",
    "        ans = [True] * len(queries)\n",
    "        for i, (l, r, k) in enumerate(queries):\n",
    "            if k < 13:\n",
    "                t = sum((x - y) & 1 for x, y in zip(preSums[r + 1], preSums[l]))\n",
    "                ans[i] = t - 2 * k <= (r + 1 - l) % 2\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canMakePaliQueries(self, s: str, queries: List[List[int]]) -> List[bool]:\n",
    "        n = len(s)\n",
    "        ps = [None] * (n + 1)\n",
    "        c = [0] * 26\n",
    "        ps[0] = tuple(c)\n",
    "        for i, v in enumerate(s, start=1):\n",
    "            v = ord(v) - ord('a')\n",
    "            c[v] ^= 1\n",
    "            ps[i] = tuple(c)\n",
    "        def ch(l, r, k):\n",
    "            d = 0\n",
    "            for i in range(26):\n",
    "                if ps[r][i] ^ ps[l][i]:\n",
    "                    d += 1\n",
    "                    if d > k:\n",
    "                        return False\n",
    "            return True\n",
    "        return [ch(l, r + 1, (k << 1) + 1) for l, r, k in queries]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "class Solution:\n",
    "    def canMakePaliQueries(self, s: str, queries: List[List[int]]) -> List[bool]:\n",
    "        from collections import defaultdict\n",
    "        # build prefix sum\n",
    "        count = defaultdict(list)\n",
    "        for i in range(26):\n",
    "            ch = chr(97+i)\n",
    "            count[ch].append(0)\n",
    "            for j in range(len(s)):\n",
    "                if s[j] == ch:\n",
    "                    count[ch].append(count[ch][-1]+1)\n",
    "                else:\n",
    "                    count[ch].append(count[ch][-1])\n",
    "\n",
    "        ans = []\n",
    "        for left, right, k in queries:\n",
    "            odd = 0\n",
    "            for i in range(26):\n",
    "                ch = chr(97+i)\n",
    "                amount = count[ch][right+1] - count[ch][left]\n",
    "                if amount%2 != 0:\n",
    "                    odd += 1\n",
    "            ans.append(odd == 1 or odd - 2*k <= 1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canMakePaliQueries(self, s: str, queries: List[List[int]]) -> List[bool]:\n",
    "        n = len(s)\n",
    "        pre = [[0] * (n+1) for _ in range(26)]\n",
    "        for i,x in enumerate(s):\n",
    "            cur = ord(x) - ord('a')\n",
    "            for y in range(26):\n",
    "                pre[y][i+1] = pre[y][i]\n",
    "                if cur == y:\n",
    "                    pre[y][i+1] += 1\n",
    "\n",
    "        ans = []\n",
    "        for l,r,k in queries:\n",
    "            m = 0\n",
    "            for i in range(26):\n",
    "                if (pre[i][r+1] - pre[i][l]) % 2 == 1:\n",
    "                    m += 1\n",
    "            ans.append(m//2 <=k)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "第一次错误原因：\n",
    "可以重新排列子串\n",
    "\"\"\"\n",
    "class Solution:\n",
    "    def canMakePaliQueries(self, s: str, queries: List[List[int]]) -> List[bool]:\n",
    "        tl=[0]*26\n",
    "        pre_c=[tuple(tl)]\n",
    "        \n",
    "        \n",
    "        for ts in s:\n",
    "            tl[ord(ts)-ord('a')]+=1\n",
    "            pre_c.append(tuple(tl))\n",
    "        ans=[]\n",
    "        # print(pre_c)\n",
    "        for tl,tr,k in queries:\n",
    "            \n",
    "            tk=0\n",
    "            tll=pre_c[tl]\n",
    "            trl=pre_c[tr+1]\n",
    "            ts=0\n",
    "            for i in range(26):\n",
    "                tk+=(trl[i]-tll[i])%2\n",
    "                ts+=(trl[i]-tll[i])\n",
    "            # print(tk,ts)\n",
    "            if ts%2==0 :##偶数\n",
    "                ans.append(k>=(tk//2+tk%2))\n",
    "            else:\n",
    "                ans.append(k>=tk//2)\n",
    "        return ans\n",
    "                    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canMakePaliQueries(self, s: str, queries: List[List[int]]) -> List[bool]:\n",
    "        # 题目注意：可以对子串进行重新排列，并最多替换k项（不能连续替换同一项超过一次）为任意小写英文字母，检测排列替换后的字符串是否为回文字符串\n",
    "        # 情况1.子串中每个字母个数都为偶数，无需替换\n",
    "        # 情况2.子串中m(m>=1)个字母个数为奇数,只需替换m/2向下取整即m//2次就能变成回文串\n",
    "        # 如何多次快速求出子串中每种字母的个数？~~~显而易见前缀和\n",
    "        pre_sum = [[0] * 26]  # pre_sum[i][j]表示从s[0]到s[i]中每个字母chr(j+ord(a))出现的次数\n",
    "        for char in s:\n",
    "            # 切片复制数组末尾数组，并用当前字符char更新复制数组中的对应字母个数，此时复制数组为末尾元素\n",
    "            pre_sum.append(pre_sum[-1][::])\n",
    "            pre_sum[-1][ord(char) - ord('a')] += 1\n",
    "\n",
    "        ans = []\n",
    "        for l, r, k in queries:\n",
    "            n = 0  # 统计子串中有多少字母出现奇数次\n",
    "            # 由于第一个元素是无效数组，所以实际数组长度为真实数组长度加一，所以l-1变为l，r变为r+1\n",
    "            for sl, sr in zip(pre_sum[l], pre_sum[r + 1]):  # sl为下标0~l（包含边界）所有字母出现次数\n",
    "                n += (sr - sl) % 2  # sr-sl分别为每个字母在l到r出现次数，奇数+1，偶数+0\n",
    "            ans.append(n // 2 <= k)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canMakePaliQueries(self, s: str, queries: List[List[int]]) -> List[bool]:\n",
    "        res=[]\n",
    "        n=len(s)\n",
    "        row=[0]*26\n",
    "        s_list=[row]\n",
    "        begin=ord('a')\n",
    "        for i in range(n):\n",
    "            tmp_row=s_list[i].copy()\n",
    "            tmp_row[ord(s[i])-begin]+=1\n",
    "            s_list.append(tmp_row)\n",
    "        # print(s_list)\n",
    "\n",
    "        for i,j,k in queries:\n",
    "            delta_list=[s_list[j+1][nnnn]-s_list[i][nnnn] for nnnn in range(26)]\n",
    "            res.append(self.checkPal(delta_list,k,j-i+1))\n",
    "        \n",
    "        return res\n",
    "\n",
    "    def checkPal(self, s_list,k,n):\n",
    "        nn=n//2\n",
    "        if nn<=k:\n",
    "            return True\n",
    "\n",
    "\n",
    "        un_match_count=0\n",
    "        for v in s_list:\n",
    "            un_match_count+=v%2\n",
    "        \n",
    "        if un_match_count//2<=k:\n",
    "            return True\n",
    "        else:\n",
    "            return False\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canMakePaliQueries(self, s: str, queries: List[List[int]]) -> List[bool]:\n",
    "        n = len(s)\n",
    "        count=[False]*26\n",
    "        co=[False]*26\n",
    "        p=ord('a')\n",
    "        for i in range(n):\n",
    "            t=ord(s[i])-p\n",
    "            co[t]=not co[t]\n",
    "            count. extend(co)\n",
    "        res = []\n",
    "        bits=0\n",
    "        for l, r, k in queries:\n",
    "            if r==l:\n",
    "                    res.append(True)\n",
    "                    continue           \n",
    "            bits=0\n",
    "            l=l*26\n",
    "            r= r*26-l+26       \n",
    "            for i in range(l, l+26):\n",
    "               # print(count[r][i],count[r][l])\n",
    "                 bits+=count[i+r]^count[i]\n",
    "            res.append(bits -1<= k<<1 ) \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canMakePaliQueries(self, s: str, queries: List[List[int]]) -> List[bool]:\n",
    "        _sum = [[0] for i in range(26)]\n",
    "        ans = []\n",
    "        for i in s:\n",
    "            for j in range(26):\n",
    "                if ord(i) - ord('a') == j:\n",
    "                    t = _sum[j][-1]\n",
    "                    _sum[j].append(t + 1)\n",
    "                else:\n",
    "                    t = _sum[j][-1]\n",
    "                    _sum[j].append(t)\n",
    "        for q in queries:\n",
    "            l, r, k = q[0], q[1], q[2]\n",
    "            tmp = [_sum[i][r+1] - _sum[i][l] for i in range(26)]\n",
    "            tmp = [x%2 for x in tmp]\n",
    "            if (r-l)%2 == 0:\n",
    "                k += 1\n",
    "            if sum(tmp) <= 2*k:\n",
    "                ans.append(True)\n",
    "            else:\n",
    "                ans.append(False)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import numpy as np\n",
    "class Solution:\n",
    "    def canMakePaliQueries(self, s: str, queries: List[List[int]]) -> List[bool]:\n",
    "        # 对每个字母的数量做前缀和\n",
    "        n = len(s)\n",
    "        pres = np.zeros((26, n), dtype=np.int32)\n",
    "        for i in range(n):\n",
    "            pres[ord(s[i]) - ord('a')][i] = 1\n",
    "            if i > 0:\n",
    "                pres[:, i] += pres[:, i - 1]\n",
    "        \n",
    "        # print(repr(pres))\n",
    "        def qu(l, r):\n",
    "            if l == 0:\n",
    "                return pres[:, r]\n",
    "            else:\n",
    "                return pres[:, r] - pres[:, l - 1]\n",
    "        \n",
    "        ans = []\n",
    "        for query in queries:\n",
    "            p = qu(query[0], query[1])\n",
    "            p = map(lambda x: x & 1, p)\n",
    "            p = reduce(lambda x, y: x + y, p, 0)\n",
    "            k = query[2]\n",
    "            if p <= 2 * k + 1:\n",
    "                ans.append(True)\n",
    "            else:\n",
    "                ans.append(False)\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canMakePaliQueries(self, s: str, queries: List[List[int]]) -> List[bool]:\n",
    "        ret = []\n",
    "        \n",
    "        ab = []\n",
    "        temp_ab = [0]*26\n",
    "        ab.append([t for t in temp_ab])\n",
    "        for i in range(len(s)):\n",
    "            temp_ab[ord(s[i]) - ord('a')] += 1\n",
    "            ab.append([t for t in temp_ab])\n",
    "        \n",
    "        for q in queries:\n",
    "            count_ab = [ab[q[1]+1][i] - ab[q[0]][i] for i in range(26)]\n",
    "            count_ab = [t%2 for t in count_ab]\n",
    "            ret.append(bool(sum(count_ab)//2 <= q[2]))\n",
    "        return ret\n",
    "    \n",
    "        #     count_ab = 0\n",
    "        #     for c in sq:\n",
    "        #         idx = ord(c) - ord('a')\n",
    "        #         count_ab ^= 1<<idx\n",
    "        #     count_1 = 0\n",
    "        #     while count_ab:\n",
    "        #         count_1 += count_ab & 1\n",
    "        #         count_ab >>= 1\n",
    "        #     ret.append(bool(count_1//2 <= q[2]))\n",
    "        # return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canMakePaliQueries(self, s: str, queries: List[List[int]]) -> List[bool]:\n",
    "        n = len(s)\n",
    "        res = []\n",
    "        pre_sum = [[0]*26]\n",
    "        for i in range(n):\n",
    "            cha = s[i]\n",
    "            new_sum = copy.deepcopy(pre_sum[-1])\n",
    "            new_sum[ord(cha)-ord('a')]+=1\n",
    "            pre_sum.append(new_sum)\n",
    "        # print(pre_sum)\n",
    "        for l,r,k in queries:\n",
    "            num_odd = 0\n",
    "            for i in range(26):\n",
    "                if (pre_sum[r+1][i]-pre_sum[l][i])%2:\n",
    "                    num_odd+=1\n",
    "            print(num_odd)\n",
    "            if num_odd-(r-l+1)%2<=2*k:\n",
    "                res.append(True)\n",
    "            else:\n",
    "                res.append(False)\n",
    "        return res\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canMakePaliQueries(self, s: str, queries: List[List[int]]) -> List[bool]:\n",
    "        from copy import copy\n",
    "        sList = [0 for _ in range(26)]\n",
    "        infoDict = {}\n",
    "        infoDict[-1] = copy(sList)\n",
    "        for i, pi in enumerate(s):\n",
    "            idx = ord(pi)-97\n",
    "            sList[idx] = 1-sList[idx]\n",
    "            infoDict[i] = copy(sList)\n",
    "        re = []\n",
    "        for pi in queries:\n",
    "            dif = 0\n",
    "            statInfo = infoDict[pi[0]-1]\n",
    "            endInfo = infoDict[pi[1]]\n",
    "            for pj in range(26):\n",
    "                if not endInfo[pj]-statInfo[pj]:\n",
    "                    continue\n",
    "                dif += 1\n",
    "            dif = int(dif/2)\n",
    "            if pi[2]<dif:\n",
    "                re.append(False)\n",
    "            else:\n",
    "                re.append(True)\n",
    "        return re"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    #可以重新排序 也就是要计算序列中每个字符的出现频率\n",
    "    def canMakePaliQueries(self, s: str, queries: List[List[int]]) -> List[bool]:\n",
    "        dic = {}\n",
    "        cur = [0 for i in range(26)]\n",
    "        dic[0] = tuple(cur)\n",
    "        for i, a in enumerate(s):\n",
    "            cur[ord(a)-ord('a')] += 1\n",
    "            dic[i + 1] = tuple(cur)\n",
    "\n",
    "        ans = []\n",
    "        for l, r, k in queries:\n",
    "            cur1 = dic[l]\n",
    "            cur2 = dic[r+1]\n",
    "            val = 0\n",
    "            for a, b in zip(cur1,cur2):\n",
    "                if (b-a)%2 == 1:\n",
    "                    val += 1\n",
    "            #val代表成单出现的数目\n",
    "            if (r-l+1)%2 == 1:\n",
    "                val -= 1#当长度为奇数时，可以视作val-1 因为有一个可以放在正中心  剩下的值val必定是个偶数,将之除以2即为所需的最少次数\n",
    "            val = val // 2\n",
    "            if val <= k:\n",
    "                ans.append(True)\n",
    "            else:\n",
    "                ans.append(False)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def canMakePaliQueries(self, s: str, queries: List[List[int]]) -> List[bool]:\n",
    "        pref = dict()\n",
    "        pref[0] = [0] * 26\n",
    "        for i, c in enumerate(s):\n",
    "            j = ord(c) - ord('a')\n",
    "            pref[i + 1] = copy.copy(pref[i])\n",
    "            pref[i + 1][j] += 1\n",
    "        ans = []\n",
    "\n",
    "        for l, r, k in queries:\n",
    "            cnt = [pref[r + 1][i] - pref[l][i] for i in range(26)]\n",
    "            # print(cnt)\n",
    "            odd_cnt = sum(cnt[i] % 2 for i in range(26))\n",
    "            # print(odd_cnt, k)\n",
    "            ans.append(odd_cnt <= k * 2 + 1 or odd_cnt <= 1)\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canMakePaliQueries(self, s: str, queries: List[List[int]]) -> List[bool]:\n",
    "        n = len(queries)\n",
    "        ans = [False]*n\n",
    "        dic = defaultdict(list)\n",
    "        data = [0]*26\n",
    "        dic[0] = data[:]\n",
    "        for i in range(1,len(s)+1):\n",
    "            data[ord(s[i-1])-ord('a')] += 1\n",
    "            dic[i] = data[:]\n",
    "        #print(dic)\n",
    "        for i in range(n):\n",
    "            cnt = 0\n",
    "            d1 = dic[queries[i][0]]\n",
    "            d2 = dic[queries[i][1]+1]\n",
    "            k = queries[i][2]\n",
    "            #print(d2,d1,queries[i])\n",
    "            \n",
    "            for j in range(26):\n",
    "                if (d2[j] - d1[j]) % 2 != 0:\n",
    "                    cnt += 1\n",
    "            if cnt == 0 or cnt - (k*2) <= 1:\n",
    "                ans[i] = True\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canMakePaliQueries(self, s: str, queries: List[List[int]]) -> List[bool]:\n",
    "        n = len(queries)\n",
    "        ans = [False] * n\n",
    "        sm = [[0] * 26]\n",
    "        for c in s:\n",
    "            sm.append(sm[-1].copy())\n",
    "            sm[-1][ord(c) - ord('a')] ^= 1\n",
    "        @cache\n",
    "        def f(l, r, k):\n",
    "            cnt = 0\n",
    "            for i in range(26):\n",
    "                cnt += sm[r + 1][i] ^ sm[l][i]\n",
    "            return k >= cnt // 2\n",
    "        for i in range(n):\n",
    "            ans[i] = f(queries[i][0], queries[i][1], queries[i][2])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canMakePaliQueries(self, s: str, queries: List[List[int]]) -> List[bool]:\n",
    "        check = [[] for _ in range(26)]\n",
    "        for i in range(26):\n",
    "            check[i].append(0)\n",
    "        \n",
    "        for c in s:\n",
    "            for i in range(26):\n",
    "                if ord(c) - 97 == i:\n",
    "                    check[i].append(check[i][-1] + 1)\n",
    "                else:\n",
    "                    check[i].append(check[i][-1])\n",
    "\n",
    "        ans = []\n",
    "        for query in queries:\n",
    "            left, right, k = query[0], query[1], query[2]\n",
    "            odds = 0\n",
    "            for i in range(26):\n",
    "                if (check[i][right+1] - check[i][left]) % 2 == 1:\n",
    "                    odds += 1\n",
    "            \n",
    "            if odds // 2 <= k:\n",
    "                ans.append(True)\n",
    "            else:\n",
    "                ans.append(False)\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canMakePaliQueries(self, s: str, queries: List[List[int]]) -> List[bool]:\n",
    "        sum = [[0] * 26]\n",
    "        for c in s:\n",
    "            sum.append(sum[-1].copy())\n",
    "            sum[-1][ord(c) - ord('a')] += 1\n",
    "\n",
    "        @cache\n",
    "        def compute(left, right, k):\n",
    "            m = 0\n",
    "            for sl, sr in zip(sum[left], sum[right + 1]):\n",
    "                m += (sr - sl) % 2\n",
    "            \n",
    "            return m // 2 <= k\n",
    "        res = []\n",
    "        for left, right, k in queries:\n",
    "            res.append(compute(left, right, k))\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canMakePaliQueries(self, s: str, queries: List[List[int]]) -> List[bool]:\n",
    "        n = len(queries)\n",
    "        ans = [False] * n\n",
    "        sm = [[0] * 26]\n",
    "        for c in s:\n",
    "            sm.append(sm[-1].copy())\n",
    "            sm[-1][ord(c) - ord('a')] += 1\n",
    "        @cache\n",
    "        def f(l, r, k):\n",
    "            cnt = 0\n",
    "            for i in range(26):\n",
    "                cnt += (sm[r + 1][i] - sm[l][i]) % 2\n",
    "            return k >= cnt // 2\n",
    "        for i in range(n):\n",
    "            ans[i] = f(queries[i][0], queries[i][1], queries[i][2])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canMakePaliQueries(self, s: str, queries):\n",
    "        a = set([y[0] for y in queries])\n",
    "        a.update(set([x[1]+1 for x in queries]))\n",
    "        temp = [0]*26\n",
    "        count = {0:list(temp)}\n",
    "        ans = []\n",
    "        visited = {}\n",
    "        for i in range(len(s)):\n",
    "            c = s[i]\n",
    "            temp[ord(c) - ord('a')] += 1\n",
    "            if i + 1 in a:\n",
    "                count[i+1] = list(temp)\n",
    "        for x in queries:\n",
    "            start = x[0]\n",
    "            end = x[1]+1\n",
    "            if (start,end) in visited: temp = visited[(start,end)]\n",
    "            else:\n",
    "                temp = sum(abs(count[start][i] - count[end][i])%2 for i in range(26))//2\n",
    "                visited[(start,end)] = temp\n",
    "            if temp <= x[2]:\n",
    "                ans.append(True)\n",
    "            else:\n",
    "                ans.append(False)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canMakePaliQueries(self, s, queries):\n",
    "        res = []\n",
    "        index = []\n",
    "        for i in range(-1,len(s)):\n",
    "            index.append(i)\n",
    "        \n",
    "        numchar = []\n",
    "        for i in range(26):\n",
    "            numchar.append(0)\n",
    "        numchars = []\n",
    "        numchar2 = [c for c in numchar]\n",
    "        numchars.append(numchar2)\n",
    "        \n",
    "        for i in range(len(s)):\n",
    "            numchar[ord(s[i])-97] += 1\n",
    "            numchar2 = [c for c in numchar]\n",
    "            numchars.append(numchar2)\n",
    "            \n",
    "        \n",
    "        numcharsdict = dict(zip(index, numchars))\n",
    "        \n",
    "        for i in range(len(queries)):\n",
    "            curcharnum = 0\n",
    "            curstrcharsum = 0\n",
    "            for j in range(26):\n",
    "                curcharnum = numcharsdict[queries[i][1]][j] - numcharsdict[queries[i][0]-1][j]\n",
    "                if curcharnum % 2 == 1:\n",
    "                    curstrcharsum += 1\n",
    "            \n",
    "            if curstrcharsum % 2 == 1:\n",
    "                if (curstrcharsum-1)/2 <= queries[i][2]:\n",
    "                    res.append(True)\n",
    "                else:\n",
    "                    res.append(False)\n",
    "            else:\n",
    "                if curstrcharsum/2 <= queries[i][2]:\n",
    "                    res.append(True)\n",
    "                else:\n",
    "                    res.append(False)\n",
    "            curstrcharsum = 0\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canMakePaliQueries(self, s: str, queries: List[List[int]]) -> List[bool]:\n",
    "        import numpy\n",
    "        counts,cri = [],[0] * 26\n",
    "        for c in s:\n",
    "            cri[ord(c) - 97] += 1\n",
    "            counts.append(cri[:])\n",
    "        # print(counts)\n",
    "        ans = []\n",
    "        for query in queries:\n",
    "            if query[0] == 0:\n",
    "                current = counts[query[1]]\n",
    "            else:\n",
    "                current = list(numpy.array(counts[query[1]]) - numpy.array(counts[query[0]-1]))\n",
    "            odd = 0\n",
    "            for ele in current:\n",
    "                if ele % 2: odd += 1\n",
    "            # print(odd,current)\n",
    "            odd -= query[2] * 2\n",
    "            if odd <= 1:\n",
    "                ans.append(True)\n",
    "            else:\n",
    "                ans.append(False)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canMakePaliQueries(self, s: str, queries: List[List[int]]) -> List[bool]:\n",
    "        n = len(s)\n",
    "        count=[[0]*26]\n",
    "        co=[0]*26\n",
    "        p=ord('a')\n",
    "        for i in range(n):\n",
    "            t=ord(s[i])-p\n",
    "            co[t]=co[t]^1\n",
    "            count. append(copy. deepcopy(co))\n",
    "       \n",
    "        res = []\n",
    "        print(count)\n",
    "        bits=0\n",
    "        for l, r, k in queries:\n",
    "            if r==l:\n",
    "                    res.append(True)\n",
    "                    continue           \n",
    "            bits=0\n",
    "               \n",
    "            for i in range(26):\n",
    "                \n",
    "               # print(count[r][i],count[r][l])\n",
    "                bits+= count[r+1][i]^ count[l][i]\n",
    "                       \n",
    "            res.append(bits -1<= k<<1 ) \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canMakePaliQueries(self, s: str, queries: List[List[int]]) -> List[bool]:\n",
    "        n = len(s)\n",
    "        count=[[0]*26]\n",
    "        co=[0]*26\n",
    "        p=ord('a')\n",
    "        for i in range(n):\n",
    "            t=ord(s[i])-p\n",
    "            co[t]=co[t]^1\n",
    "            count. append(copy. deepcopy(co))\n",
    "       \n",
    "        res = []\n",
    "        print(count)\n",
    "        bits=0\n",
    "        for l, r, k in queries:\n",
    "                  \n",
    "            bits=0\n",
    "               \n",
    "            for i in range(26):\n",
    "                \n",
    "               # print(count[r][i],count[r][l])\n",
    "                bits+= count[r+1][i]^ count[l][i]\n",
    "                       \n",
    "            res.append(bits -1<= k<<1 ) \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import numpy\n",
    "class Solution:\n",
    "    def canMakePaliQueries(self, s: str, queries: List[List[int]]) -> List[bool]:\n",
    "        prefix_count = [numpy.array([0] * 26)]\n",
    "        \n",
    "        for i in range(len(s)):\n",
    "            cur_count = prefix_count[-1].copy()\n",
    "            cur_count[ord(s[i]) - 97] += 1\n",
    "            prefix_count.append(cur_count)\n",
    "        \n",
    "        res = []\n",
    "        for left, right, k in queries:\n",
    "            count = numpy.subtract(prefix_count[right + 1], prefix_count[left])\n",
    "            odd_num = sum(1 for val in count if val % 2 == 1)\n",
    "            res.append((odd_num - 2 * k) <= 1)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import numpy\n",
    "class Solution:\n",
    "    def canMakePaliQueries(self, s: str, queries: List[List[int]]) -> List[bool]:\n",
    "        prefix_count = [numpy.array([0] * 26)]\n",
    "        \n",
    "        for i in range(len(s)):\n",
    "            cur_count = prefix_count[-1].copy()\n",
    "            cur_count[ord(s[i]) - 97] += 1\n",
    "            prefix_count.append(cur_count)\n",
    "        \n",
    "        res = []\n",
    "        calculated = {}\n",
    "        for left, right, k in queries:\n",
    "            if (left, right) not in calculated:\n",
    "                count = numpy.subtract(prefix_count[right + 1], prefix_count[left])\n",
    "                odd_num = sum(1 for val in count if val % 2 == 1)\n",
    "                calculated[(left, right)] = odd_num\n",
    "            else:\n",
    "                odd_num = calculated[(left, right)]\n",
    "            res.append((odd_num - 2 * k) <= 1)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import numpy\n",
    "class Solution:\n",
    "    def canMakePaliQueries(self, s: str, queries: List[List[int]]) -> List[bool]:\n",
    "        prefix_count = [numpy.array([0] * 26)]\n",
    "        \n",
    "        for i in range(len(s)):\n",
    "            cur_count = prefix_count[-1].copy()\n",
    "            cur_count[ord(s[i]) - 97] += 1\n",
    "            prefix_count.append(cur_count)\n",
    "        \n",
    "        res = []\n",
    "        calculated = {}\n",
    "        for left, right, k in queries:\n",
    "            if (left, right) not in calculated:\n",
    "                count = numpy.subtract(prefix_count[right + 1], prefix_count[left])\n",
    "                odd_num = sum(1 for val in count if val % 2 == 1)\n",
    "                calculated[(left, right)] = odd_num\n",
    "            else:\n",
    "                odd_num = calculated[(left, right)]\n",
    "            res.append((odd_num - 2 * k) <= 1)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import numpy\n",
    "class Solution:\n",
    "    def canMakePaliQueries(self, s: str, queries: List[List[int]]) -> List[bool]:\n",
    "        prefix_count = [numpy.array([0] * 26)]\n",
    "        \n",
    "        for i in range(len(s)):\n",
    "            cur_count = prefix_count[-1].copy()\n",
    "            ascii_val = ord(s[i]) - 97\n",
    "            cur_count[ascii_val] = not cur_count[ascii_val]\n",
    "            prefix_count.append(cur_count)\n",
    "        \n",
    "        res = []\n",
    "        calculated = {}\n",
    "        for left, right, k in queries:\n",
    "            if (left, right) not in calculated:\n",
    "                count = numpy.subtract(prefix_count[right + 1], prefix_count[left])\n",
    "                odd_num = sum(abs(val) for val in count)\n",
    "                calculated[(left, right)] = odd_num\n",
    "            else:\n",
    "                odd_num = calculated[(left, right)]\n",
    "            res.append((odd_num - 2 * k) <= 1)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canMakePaliQueries(self, s: str, queries: List[List[int]]) -> List[bool]:\n",
    "        # res = []\n",
    "        # for q in queries:\n",
    "        #     ss = s[q[0]:q[1]+1]\n",
    "        #     k = [0 for _ in range(26)]\n",
    "        #     for sss in ss:\n",
    "        #         k[ord(sss)-ord('a')] += 1\n",
    "        #     print(k)\n",
    "        # #     val = 0\n",
    "        # #     for kk in k:\n",
    "        # #         val += kk%2\n",
    "        # #     if val//2 <= q[2]:\n",
    "        # #         res.append(True)\n",
    "        # #     else:\n",
    "        # #         res.append(False)\n",
    "        # # return res\n",
    "    \n",
    "        n = len(s)\n",
    "        f = [[0] * 26 for _ in range(n + 1)]\n",
    "        for i in range(n):\n",
    "            for j in range(26):\n",
    "                f[i + 1][j] = f[i][j]\n",
    "            f[i + 1][ord(s[i]) - ord('a')] += 1\n",
    "        print(f)\n",
    "        ans = []\n",
    "        for p, q, m in queries:\n",
    "            t = 0\n",
    "            for i in range(26):\n",
    "                if (f[q + 1][i] - f[p][i]) % 2 != 0:\n",
    "                    t += 1\n",
    "            ans.append(m >= t // 2)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution(object):\n",
    "    def canMakePaliQueries(self, s, queries):\n",
    "        \"\"\"\n",
    "        :type s: str\n",
    "        :type queries: List[List[int]]\n",
    "        :rtype: List[bool]\n",
    "        \"\"\"\n",
    "        top_n_set = []\n",
    "        temp_set = set()\n",
    "        for si in s :\n",
    "            if si in temp_set :\n",
    "                temp_set.remove(si)\n",
    "            else :\n",
    "                temp_set.add(si)\n",
    "            top_n_set.append(set([t for t in temp_set]))\n",
    "        \n",
    "        def countc(s, e) :\n",
    "            set_s = top_n_set[s-1] if s > 0 else set()\n",
    "            set_e = top_n_set[e]\n",
    "            return (len(set_s) + len(set_e) - 2*len(set_e & set_s)) // 2\n",
    "            # return (len(set_s | set_e) - len(set_s & set_e)) // 2\n",
    "        to_ret = [countc(t[0],t[1]) <= t[2] for t in queries]\n",
    "        return to_ret\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canMakePaliQueries(self, s: str, queries: List[List[int]]) -> List[bool]:\n",
    "        #计算到每个位置的奇数字母个数\n",
    "        X=[]\n",
    "        n=len(s)\n",
    "        cur=set()\n",
    "        for i in range(n):\n",
    "            if(s[i] in cur):\n",
    "                cur.remove(s[i])\n",
    "            else:\n",
    "                cur.add(s[i])\n",
    "            X.append(cur.copy())\n",
    "        i=0\n",
    "        for left,right,k in queries:\n",
    "            x=len(X[left-1] ^ X[right]) if left>0 else len(X[right])\n",
    "            #print(x)\n",
    "            x=x//2 if((right-left+1)%2==0) else (x-1)//2 #偶数个\n",
    "            queries[i]=(x<=k)\n",
    "            i+=1\n",
    "        return queries\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canMakePaliQueries(self, s: str, queries: List[List[int]]) -> List[bool]:\n",
    "        # 集合 + 前缀和的思想\n",
    "        # a[k]记录字符串s[0:k]的字符出现情况（这里只需要记录单数情况，因为偶数总能重排成回文结构\n",
    "        a = [set() for _ in range(len(s) + 1)] \n",
    "        d = set()\n",
    "        for i, c in enumerate(s, 1):\n",
    "            if c in d:\n",
    "                d.remove(c)\n",
    "            else:\n",
    "                d.add(c)\n",
    "            a[i] = d.copy()\n",
    "        \n",
    "        def check(l: int, r: int, change: int):\n",
    "            res = a[l].union(a[r + 1]) - a[l].intersection(a[r+1])\n",
    "            if change >= (len(res) // 2):\n",
    "                return True\n",
    "            return False\n",
    "        \n",
    "        return [check(left, right, k) for left, right, k in queries]\n",
    "            \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canMakePaliQueries(self, s: str, queries: List[List[int]]) -> List[bool]:\n",
    "        status = [None]*(len(s)+1)\n",
    "        status[0] = set()\n",
    "        chset = set()\n",
    "        for i, ch in enumerate(s):\n",
    "            if ch in chset:\n",
    "                chset.remove(ch)\n",
    "            else:\n",
    "                chset.add(ch)\n",
    "            status[i+1] = chset.copy()\n",
    "\n",
    "        res = [False]*len(queries)\n",
    "        for i, q in enumerate(queries):\n",
    "            s1, s2 = status[q[1]+1], status[q[0]]\n",
    "            val = len(s1) + len(s2) - 2*len(s1&s2)\n",
    "            res[i] = val//2 <= q[2]\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canMakePaliQueries(self, s: str, queries: List[List[int]]) -> List[bool]:\n",
    "        pres = [{s[0]}]\n",
    "        n = len(s)\n",
    "        for i in range(1, n):\n",
    "            c = s[i]\n",
    "            pres.append((pres[-1] - {c}) if c in pres[-1] else (pres[-1] | {c}))\n",
    "        return [len(\n",
    "            ((pres[right] | pres[left - 1]) - (pres[right] & pres[left - 1])) if left else pres[right]) // 2 <= max_num\n",
    "                for left, right, max_num in queries]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def get_all(self, s):\n",
    "        mp = {}\n",
    "        _set = set()\n",
    "        mp[-1] = _set.copy()\n",
    "        for i, item in enumerate(s):\n",
    "            if item not in _set:\n",
    "                _set.add(item)\n",
    "            else:\n",
    "                _set.remove(item)\n",
    "            mp[i] = _set.copy()\n",
    "        return mp\n",
    "\n",
    "    def canMakePaliQueries(self, s: str, queries: List[List[int]]) -> List[bool]:\n",
    "        ans = []\n",
    "        mp = self.get_all(s)\n",
    "        # print(mp)\n",
    "        for querie in queries:\n",
    "            left_set = mp[querie[0] - 1]\n",
    "            right_set = mp[querie[1]]\n",
    "            cnt = len(right_set)\n",
    "            for item in left_set:\n",
    "                if item not in right_set:\n",
    "                    cnt += 1\n",
    "                else:\n",
    "                    cnt -= 1\n",
    "            if (querie[1] - querie[0] + 1) % 2:\n",
    "                cnt -= 1\n",
    "            cnt //= 2\n",
    "            ans.append(cnt <= querie[2])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canMakePaliQueries(self, s: str, queries: List[List[int]]) -> List[bool]:\n",
    "        str_dict={-1:set()}\n",
    "        for i in range(len(s)):\n",
    "            str_dict[i]=set(str_dict[i-1])\n",
    "            if s[i] in str_dict[i]:\n",
    "                str_dict[i].remove(s[i])\n",
    "            else:\n",
    "                str_dict[i].add(s[i])\n",
    "        def get_change_num(begin_index,end_index):\n",
    "            change_num=0\n",
    "            for char in str_dict[begin_index].union(str_dict[end_index]):\n",
    "                if not(char in str_dict[begin_index] and char in str_dict[end_index]):\n",
    "                    change_num+=1\n",
    "            return change_num//2\n",
    "        \n",
    "        results=list()\n",
    "        for query in queries:\n",
    "            if query[2]>=get_change_num(query[0]-1,query[1]):\n",
    "                results.append(True)\n",
    "            else:\n",
    "                results.append(False)\n",
    "        return results"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import numpy\n",
    "class Solution:\n",
    "    def canMakePaliQueries(self, s: str, queries: List[List[int]]) -> List[bool]:\n",
    "        prefix_count = [numpy.array([0] * 26)]\n",
    "        \n",
    "        for i in range(len(s)):\n",
    "            cur_count = prefix_count[-1].copy()\n",
    "            cur_count[ord(s[i]) - 97] += 1\n",
    "            prefix_count.append(cur_count)\n",
    "        \n",
    "        res = []\n",
    "        calculated = {}\n",
    "        for left, right, k in queries:\n",
    "            if (left, right) not in calculated:\n",
    "                count = numpy.subtract(prefix_count[right + 1], prefix_count[left])\n",
    "                calculated[(left, right)] = count\n",
    "            else:\n",
    "                count = calculated[(left, right)]\n",
    "            odd_num = sum(1 for val in count if val % 2 == 1)\n",
    "            res.append((odd_num - 2 * k) <= 1)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canMakePaliQueries(self, s: str, queries: List[List[int]]) -> List[bool]:\n",
    "\n",
    "        record = dict.fromkeys(s)\n",
    "        for c in record:\n",
    "            record[c] = [0 for _ in range(len(s))]\n",
    "        for i in range(len(s)):\n",
    "            record[s[i]][i] = 1\n",
    "        \n",
    "        for c in record:\n",
    "            for i in range(1, len(s)):\n",
    "                record[c][i] = record[c][i]+record[c][i-1]\n",
    "\n",
    "            \n",
    "        def check(l,r,k):\n",
    "            \n",
    "            n_odd = 0\n",
    "            for c in record:\n",
    "                if l>0:\n",
    "                    if (record[c][r] - record[c][l-1])%2==1:\n",
    "                        n_odd += 1\n",
    "                else:\n",
    "                    if record[c][r]%2==1:\n",
    "                        n_odd += 1\n",
    "                           \n",
    "            if n_odd > 2*k + 1:\n",
    "                return False\n",
    "            else:\n",
    "                return True\n",
    "\n",
    "        return [check(ind[0],ind[1],ind[2]) for ind in queries]\n",
    "                    \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canMakePaliQueries(self, s: str, queries: List[List[int]]) -> List[bool]:\n",
    "        n, base = len(s), ord('a')\n",
    "        # cnt = []\n",
    "        # for i in range(26):\n",
    "        #     cnt.append(list(itertools.accumulate([1 if ord(c) - base == i else 0 for c in s], initial=0)))\n",
    "        cnt = [list(itertools.accumulate([1 if ord(c) - base == i else 0 for c in s], initial=0)) for i in range(26)]\n",
    "        for i, (left, right, k) in enumerate(queries):\n",
    "            temp_cnt = [pre[right + 1] - pre[left] for pre in cnt]\n",
    "            temp_cnt = sum(t % 2 for t in temp_cnt)\n",
    "            queries[i] = (temp_cnt >> 1) <= k\n",
    "        return queries"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canMakePaliQueries(self, s: str, queries: List[List[int]]) -> List[bool]:\n",
    "        n = len(s)\n",
    "        def f(s,c='a'):\n",
    "            tmp = [int(ch==c) for ch in s]\n",
    "            return [0]+list(accumulate(tmp))\n",
    "        cnt = []\n",
    "        for c in string.ascii_lowercase:\n",
    "            cnt.append(f(s,c))\n",
    "        ans = [True]*len(queries)\n",
    "        for i,(l,r,k) in enumerate(queries):\n",
    "            odd = even= 0\n",
    "            for j in range(26):\n",
    "                preSum = cnt[j]\n",
    "                num = preSum[r+1]-preSum[l]\n",
    "                if num&1:odd+=1\n",
    "                else:even+=1\n",
    "            if odd//2>k:\n",
    "                ans[i]=False\n",
    "        return ans\n",
    "            \n",
    "                \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canMakePaliQueries(self, s: str, queries: List[List[int]]) -> List[bool]:\n",
    "\n",
    "        cache = [[0]*(len(s)+1) for i in range(26)]\n",
    "        for i in range(len(s)):\n",
    "            cache[ord(s[i])- ord(\"a\")][i+1]=1\n",
    "\n",
    "        for j in range(1,len(s)+1):\n",
    "            for k in range(26):\n",
    "\n",
    "                cache[k][j]+=cache[k][j-1]\n",
    "        \n",
    "        result=[]\n",
    "        # print(cache)\n",
    "        for query in queries:\n",
    "            odds=0\n",
    "            for j in range(26):\n",
    "                \n",
    "                if (cache[j][query[1]+1]-cache[j][query[0]])%2==1:\n",
    "                    odds +=1\n",
    "            \n",
    "            if odds -(query[1]-query[0]+1)%2 >2*query[2] :\n",
    "                result.append(False)\n",
    "            else:\n",
    "                result.append(True)\n",
    "        return result\n",
    "\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
